package com.jhy.new2025.BinaryTree;

import java.util.ArrayDeque;

/**
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 * <p>
 * struct Node {
 * int val;
 * Node *left;
 * Node *right;
 * Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
 * 如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 * <p>
 * 初始状态下，所有 next 指针都被设置为 NULL。
 */
public class Connect {
    public Node1 connect(Node1 root) {
        ArrayDeque<Node1> deque = new ArrayDeque<>();
        if (root == null) return null;
        deque.offer(root);
        // 外层循环控制每一层是否结束
        // 内层循环控制每一层的元素是否结束
        while (!deque.isEmpty()) {
            int size = deque.size();
            // 先定义每一层元素第一个的初始位置
            // 在内层循环去定义它
            Node1 pre = null;
            while (size > 0) {
                Node1 cur = deque.poll();
                if (pre != null) {
                    // 如果前一个元素不为null 前一个元素的后续节点就是当前节点
                    // 这是内部结点之间的next
                    pre.next = cur;
                }
                pre = cur;
                if (cur.left != null) deque.offer(cur.left);
                if (cur.right != null) deque.offer(cur.right);
                size--;
            }
            // 内层循环结束后 就相当于在最后的节点了 这个null只是做了一个标记而已
            if (pre != null) {
                pre.next = null;
            }
        }
        return root;
    }
}
